package example3;

import common.ListNode;
import utils.ListNodeUtil;

//234. 回文链表
public class LeetCode234 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1,3};
        ListNode listNode = ListNodeUtil.transformArrayToListNode(arr);
        ListNodeUtil.printListNode(listNode);
        System.out.println(new Solution234_1().isPalindrome(listNode));
    }
}

//方法四：快慢指针。耗时极短，内存占用中等
class Solution234_4{
    public boolean isPalindrome(ListNode head){
        if(head == null)    return true;
        //首先拿到链表的中间节点，就是前半部分链表的尾结点
        ListNode firstHalfEnd = endOfFirstHalf(head);
        //然后翻转后半部分
        ListNode secondHalfStart = reverseListNode(firstHalfEnd.next);
        //然后让前半部分的节点和后半部分的节点遍历比较
        ListNode first = head;
        ListNode second = secondHalfStart;
        boolean result = true;
        while(second != null){
            if(second.val != first.val){
                result = false;
                break;
            }
            first = first.next;
            second = second.next;
        }
        //最后将后半部分的链表再次翻转，然后恢复原链表
        firstHalfEnd.next = reverseListNode(secondHalfStart);
        return result;
    }

    //获取链表的中间节点，也就是前半部分的尾结点
    public ListNode endOfFirstHalf(ListNode head){
        if(head == null)    return null;
        //通过快慢指针获取，慢指针一次前进一格，快指针一次前进两格
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //反转链表
    public ListNode reverseListNode(ListNode head){
        ListNode curr = head;
        ListNode prev = null;
        while(curr != null){
            ListNode tempNext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tempNext;
        }
        return prev;
    }
}

//方法三：递归，外层指针从第一个遍历，内层递归指针从最后一个遍历。耗时中等，内存占用较高
class Solution234_3{
    ListNode frontPointer;

    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }

    //recursively：递归地
    public boolean recursivelyCheck(ListNode currentNode){
        if(currentNode == null)     return true;
        if(!recursivelyCheck(currentNode.next))     return false;
        if(frontPointer.val != currentNode.val)     return false;
        frontPointer = frontPointer.next;
        return true;
    }
}

//方法二：将链表中的数存入集合或数组，然后用双索引遍历比较(这里不写)

//方法一：将链表中的值存入字符串，然后逆序比较。耗时高，内存占用较低(自己写的)
class Solution234_1 {
    public boolean isPalindrome(ListNode head) {
        if(head == null)    return false;
        StringBuilder sb = new StringBuilder();
        ListNode node = head;
        while(node != null){
            sb.append(node.val);
            node = node.next;
        }
        String str = sb.toString();
        //sb调用reverse后，原本sb的值也会改变，所以下面比较要用str
        String reverse = sb.reverse().toString();
        System.out.println(sb);
        System.out.println(str);
        System.out.println(reverse);
        return reverse.equals(str);
    }
}

